package bintree.LeetCode;
//101. 对称二叉树
/*

public class Num101_isSymmetric {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        if(root.left == null && root.right != null){
            return false;
        }
        if(root.right == null && root.left != null){
            return false;
        }
        //传入两根子树，就能判断这两颗子树是否镜像相等
        return isMirror(root.left, root.right);
    }
    //传入两根子树，就能判断这两颗子树是否镜像相等
    public boolean isMirror(TreeNode root, TreeNode subtrr){
        if(root == null && subtrr == null){
            return true;
        }
        if(root == null || subtrr == null){
            return false;
        }
        //我们只负责判断这两个根节点的值是否相等
        if(root.val != subtrr.val){
            return false;
        }

        return isMirror(root.left, subtrr.right) && isMirror(root.right, subtrr.left);
    }
}

 */

import java.util.Deque;
import java.util.LinkedList;

/**
 * 使用层序遍历判断树是否对称
 */
public class Num101_isSymmetric {

    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();

            if(t1 == null && t2 == null){
               continue;
            }

            if(t1 == null || t2 == null){
                //找到反例
                return false;
            }

            if(t1.val != t2.val){
                //找到反例
                return false;
            }
            //继续
            queue.offer(t1.left);
            queue.offer(t2.right);
            //继续
            queue.offer(t1.right);
            queue.offer(t2.left);
        }
        return true;
    }

}